1. Technical Field
The disclosed technology relates to the field of concurrently accessed data structures used by computer systems.
2. Related Art
FIG. 1 illustrates a skiplist data structure 100 as is commonly understood by one skilled in the art. The skiplist data structure 100 is a collection of sorted linked lists, each at a given “level,” that mimics the behavior of a search tree. A skiplist is usually bounded by a left-sentinel node 103 and a right-sentinel node 104, each of which has a maximum level 105. The maximum level 105 for the skiplist data structure 100 is 4. The skiplist data structure 100 contains a bottom-list-level 107 (a bottom-level linked list), a second-list-level 109, a third-list-level 111, and a maximal-list-level 113. For a non-empty skiplist, the bottom-list-level 107 links a number of nodes (such as a bottom-level node 115) in key-sort order (5, 7, 8, 13, 15, 22, 25). The skiplist data structure 100 also contains a second-level node 117 and a third-level node 119. These nodes are data nodes that contain key information, metadata about the node, and links for each level of the skiplist to which the data node is linked. The highest skiplist level to which the node is linked is the node's topLevel value. One skilled in the art will understand that in some equivalent embodiments, a node can be split to multiple nodes (or sub-nodes), one in each level, where a (sub)node in each level points to the (sub)node in the level beneath it, in addition to the succeeding node in the same level.
The list at each level, other than the bottom-list-level, is a sublist of lists at the lower levels. Each node is assigned a random toplevel, up to the maximum skiplist level, and participates in the lists up to that level. In a skiplist that maintains the traditional skiplist invariant, the number of nodes in each list decreases exponentially with the level, implying that a key can be quickly found by searching first at higher levels, skipping over large numbers of shorter nodes, and progressively working downward until a node with the desired key is found, or the bottom level is reached. Thus, the expected time complexity of skiplist operations is logarithmic in the length of the list.
The left-sentinel node 103 and the right-sentinel node 104 have the maximum allowed skiplist level, and initially, when the skiplist is empty, the right-sentinel node 104 is the successor of the left-sentinel node 103 at every level. The key for the left-sentinel node 103 is smaller, and the key for the right-sentinel node 104 is greater, than any key that may be added to the skiplist. Searching the skiplist thus begins at the left-sentinel node 103.
A skiplist is an important data structure for storing and retrieving ordered data, because it does not need to be rebalanced (as do many tree structures), because of its highly distributed nature (which helps reduce contention in concurrent applications), because of its logarithmic search characteristic.
“Lock-freedom” is a progress characteristic that guarantees that if some threads are executing method calls, and at least one thread continues taking steps, then at least one thread will complete its call. It guarantees that the system as a whole continues to make progress, but makes no progress guarantee for any individual thread.
“Wait-freedom” is a stronger progress characteristic than lock-freedom and guarantees that any thread that continues taking steps in executing a method call will eventually complete the call. One skilled in the art of concurrent programming would understand that a lock-free operation on a data structure specifies that the operation does not use locks on the data structure while still enabling other concurrent operations (some of which may not have the lock-freedom characteristic) on the data structure. Note that a lock-free operation may need to restart if it detects concurrent modifications to the data structure. Thus, in high contention situations the lock-free operation may not timely complete and will delay the thread that invoked the lock-free operation. By comparison, a wait-free operation will complete without retrying and without waiting for any locks, and will not delay the invoking thread no matter the level of contention.
For a skiplist, a wait-free Contains programmed-method is important because for the most common search structure usage patterns, the Contains operation (which tests or searches whether a key is in the skiplist) significantly dominates the Add operations, and the Add operations dominate the Remove operations. A typical pattern, for example, is 90% Contains operations, 9% Add operations, and 1% Remove operations. Thus, any improvement to the performance of the Contains operation is an improvement to the most common skiplist usage pattern. Search structures are used in many high-performance real-time applications. In such applications, it is important to have a bound on the number of steps a programmed-method call may take before returning. Wait-free programmed-methods are desirable because they can provide such bounds.
The ConcurrentSkipListMap (and . . . Set) implementation released as part of the Java® SE 6 platform is the most effective concurrent lock-free skiplist implementation known to the inventors. Although the algorithm provides a lock-free Contains programmed-method, it unfortunately does not provide a wait-free one. The Contains programmed-method participates in the cleanup of removed nodes, and during concurrent operations this cleanup is a source of contention-related delays. Because of the importance of providing a wait-free Contains operation, the ConcurrentSkipListMap provides a partial wait-free Contains operation: that is, a wait-free contains that is backed up with a lock-free one in case the key is found on a logically-deleted node.
One skilled in the art will understand that implementing concurrent data structures is complex and fraught with subtle and often unexpected difficulties and, further, that the use of synchronization mechanisms, such as locks, atomic operations, etc., can cause unexpected delays to operations on the concurrent data structure when many threads are contending for access to the data structure. Such a one will also understand that concurrent linked-list algorithms exist that use optimistic fine-grained locking for the Add and Remove operations, and a wait-free Contains operation (Heller et al., “A Lazy Concurrent List-Based Set Algorithm,” Proceedings of 9th International Conference on Principles of Distributed Systems, 2005). While one not skilled in the art may naively believe that the use of such technology could be used to implement a lock-free skiplist having a wait-free Contains operation, one skilled in the art will understand that such algorithms rely on the nodes in the list having only one link for the list. Further, such a one will understand that where there are multiple list-links (as in a lock-free skiplist node), nodes cannot be atomically inserted or removed from all of its list-levels.